package io.github.hadyang.leetcode.random;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * <p>示例:
 *
 * <p>输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明:
 *
 * <p>可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q300 {
  public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) {
      return 0;
    }

    int[] dp = new int[nums.length];

    int maxDpIndex = 0;
    dp[0] = 1;
    for (int i = 1; i < nums.length; i++) {
      int maxDp = dp[maxDpIndex];

      if (nums[i] > nums[maxDpIndex]) {
        dp[i] = maxDp + 1;
      } else if (nums[i] == nums[maxDpIndex]) {
        dp[i] = maxDp;
      } else {
        dp[i] = 1;
        for (int j = 1; j <= i; j++) {
          if (nums[i] > nums[i - j]) {
            dp[i] += dp[i - j];
            break;
          }
        }
      }

      if (dp[i] > maxDp) {
        maxDpIndex = i;
      }
    }

    return dp[maxDpIndex];
  }

  @Test
  public void test() {
    Assert.assertEquals(1, lengthOfLIS(new int[] {10}));
    Assert.assertEquals(4, lengthOfLIS(new int[] {10, 9, 2, 5, 3, 7, 101, 18}));
    Assert.assertEquals(5, lengthOfLIS(new int[] {10, 9, 2, 5, 6, 3, 7, 101, 18}));
    Assert.assertEquals(4, lengthOfLIS(new int[] {10, 9, 2, 5, 8, 3, 7, 101, 18}));
  }
}
